1. Field of the Invention
The present invention relates generally to embedded system memory and in particular relates to methods and structures for patching information (program instructions and/or data) stored in an embedded memory subsystem.
2. Related Patents
This patent is related to U.S. provisional patent application Ser. No. 60/425,470 which is hereby incorporated by reference.
3. Discussion of Related Art
Embedded computing systems are often utilized for control of various devices. The simplest of consumer electronic devices such as microwave ovens, telephones, televisions etc. often include embedded microcontrollers that provide certain forms of device control and user interfacing for the device. In commercial applications, embedded computing systems often control various forms of devices such as computing and communication devices as well as numerous other types of machines and tools generally applicable to the commercial realm.
Such embedded computer systems typically include a general or special purpose processing unit that executes programmed instructions. The program instructions are typically stored in some form of read only memory that provides a nonvolatile store for program instructions, data and configuration information. The embedded processor may fetch program instructions and read data directly from the read only memory device (“ROM”). Program instructions encoded and stored in such a ROM device are often referred to as “firmware.”
Sometimes it is necessary to provide corrections or updates to the firmware within such an embedded computing system or controller. For example, communication devices may require updating from time to time in response to protocol changes, feature enhancements, bug fixes, etc. In a manufacturing environment for devices having embedded firmware, such updates may be performed by removing an earlier ROM device and substituting a replacement ROM device with corrected firmware. In some cases, ROM memory device replacement may be performed in a field environment (i.e., at a site remote from a manufacturing context). Typically, such field replacements require a skilled engineer or technician and significant care in the procedures to replace the ROM memory component. To better address the need of field firmware updates (i.e., in situ firmware updates), various techniques and structures have been employed to enable “patching” of the firmware. However, prior update or “patching” techniques generally presented numerous rigid limitations and constraints including, in some cases, imposed a performance penalty.
Some prior patching techniques required particular program coding styles and standards in the firmware to be patched. These coding styles permit simpler patching of the program constructs. In general, such techniques focused on the ability to redirect execution of the embedded processor based on a runtime test of the validity of the subroutine or function about to be executed. Some prior patching methods utilized a validity checking table stored in an ancillary memory device where a flag and target address is associated with each subroutine or function within the embedded firmware. The firmware mechanism to call or invoke such a function or subroutine is adapted to first test an associated entry in the validity table to determine if the validity flag indicates that the subroutine or function is to be redirected to a patched version of the function. If the flag indicates that a function is invalid and the patched version is to be used, the target address associated with the validity table entry is used as an alternate location for the function or subroutine execution. Such a method unfortunately incurs significant execution and memory access overhead in that every function call must include additional program instructions to access and test the validity table entries. Further, additional memory may be required for storage of the validity table.
A related technique utilizes a so-called “double jump” scheme for accessing each function or subroutine in the ROM. A read/write random access memory device (i.e., a RAM or other re-writable memory device) is used to store a jump instruction for each function. As above, program instruction coding styles for such a solution requires that each function be accessed by first jumping to a reserved RAM location. The fixed, reserved RAM location corresponding to the desired function or subroutine would normally contain a second program instruction to jump into the actual desired function or subroutine in the ROM or may contain an address for the function to be performed. In the latter case, the address is read by the processor and then an indirect jump to that location may be performed. Patching firmware in such a structure is a simple matter of replacing the second jump instruction (or address) in the reserved RAM location with the new function (either as a jump instruction to the updated function or an address of the new function to be loaded and jumped to indirectly). As above, such double jump schemes incur additional undesirable execution and memory access overhead.
Prior techniques also include a number of hardware implementations to permit patching of firmware while reducing the potential for undesired execution and/or memory fetch overhead. In general, presently practiced hardware patch mechanisms incur other limitations and overhead. Some presently known hardware patch mechanisms require, in essence, a full mirrored memory component, equal in size to the ROM to be patched, such that each memory location may be fetched from the primary ROM or from the secondary, mirrored memory containing patched versions of functions or other information. Such a full sized, mirrored memory may be wasteful and hence costly where, as is common, the patched portions of firmware may be small by comparison to the size of the complete firmware.
Other presently known hardware approaches include techniques similar to virtual memory paging structures in which hardware components test the validity of each individual memory location or page of memory locations in the primary ROM and redirects requests for invalid locations to the secondary storage components containing patched instructions. Such a structure imposes costs of complexity in the hardware design requirements. Still other hardware approaches provide some form of look-aside or translation buffer to identify functions and subroutines for which an alternate address is to be substituted. Essentially, hardware components monitor jump instructions invoking functions or subroutines and check the look-aside or translation buffer to determine if that function is to be patched with an alternate function. If so, a modified instruction or address is provided in response to the instruction fetch operation.
While such hardware techniques may reduce execution overhead as compared to similar features implemented purely in firmware, they are generally complex and may still impose some execution overhead in that caching operations relating to program instruction fetching may be disrupted. In other words, branch pipeline logic as it is common in many present day microprocessors and microcontrollers attempting to intelligently predict branched paths of execution and thereby optimize instruction caching may be disrupted by a discontinuity in the instruction fetching sequence.
It is evident from the above discussion that a need exists for improved firmware patch structures and methods that are, at once, simple and inexpensive and reduce undesirable execution or memory fetch overhead.